package array;
import java.util.*;
class Ex31 {
    static class Solution {
        public void nextPermutation(int[] nums) {
            int len;
            if ((len = nums.length) == 1) return;
            int min = len - 1, idx = len - 1;
            int i;
            for (i = len - 2; i >= 0; i--) {
                if (nums[i] > nums[i + 1]) continue;
                else {
                    int t = nums[i];
                    idx = i + 1;
                    while (idx < len) {
                        if (nums[idx] > nums[i]) idx++;
                        
                    }
                    nums[i] = nums[i + 1];
                    nums[i + 1] = t;
                    reverse(nums, i + 1, len - 1);
                    return;
                }
            }
            if (i < 0) {
                reverse(nums, 0, len - 1);
            }
        }

        public void reverse(int[] nums, int lo, int hi) {
            // int mid = (lo + hi) / 2;
            while (lo < hi) {
                int t = nums[lo];
                nums[lo] = nums[hi];
                nums[hi] = t;
                lo++;
                hi--; 
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int nums[] = new int[] {1,2,4,5,3};
        solution.nextPermutation(nums);
        // solution.reverse(nums, 2, 4);
        System.out.println(Arrays.toString(nums));
    }
}

